package algorithm.leetcode.I1201to1400;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Q1338 {

    public int minSetSize(int[] arr) {
        Map<Integer, Integer> dict = new HashMap<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[1]-o1[1]);
        int res = 0, count = 0;

        for (int j : arr) {
            dict.put(j, dict.getOrDefault(j, 0) + 1);
        }

        for (Map.Entry<Integer, Integer> entry : dict.entrySet()) {
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }

        while (2*count < arr.length && !pq.isEmpty()) {
            count += pq.poll()[1];
            res += 1;
        }
        return res;
    }

}
